//矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2
//][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。 
//
// 给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
//输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,2
//5,68,4],[84,28,14,11,5,50]]
//输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66]
//,[84,28,75,33,55,68]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 100 
// 1 <= mat[i][j] <= 100 
// 
//
// Related Topics 数组 矩阵 排序 👍 110 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author ldltd
 * @date 2024-04-29 12:43:16
 * @description 1329.将矩阵按对角线排序
 */
public class SortTheMatrixDiagonally{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SortTheMatrixDiagonally fun=new SortTheMatrixDiagonally();
	 	 Solution solution = fun.new Solution();
		 int[][] ints = {{3, 3, 1, 1}, {2, 2, 1, 2}, {1, 1, 1, 2}};
		 solution.diagonalSort(ints);
		 Arrays.stream(ints).forEach(e->{
			 System.out.println(Arrays.toString(e));
		 });
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] diagonalSort1(int[][] mat) {
		for (int i = 0; i < mat[0].length; i++) {
			ArrayList<Integer> list = new ArrayList<>();
			int r=0,c=i;
			while (!isOut(r,c,mat)){
				list.add(mat[r][c]);
				c++;
				r++;
			}
			Collections.sort(list);
			 r=0;
			 c=i;
			while (!isOut(r,c,mat)){
				mat[r][c]=list.get(r);
				c++;
				r++;
			}
		}
		for (int i = 1; i < mat.length; i++) {
			ArrayList<Integer> list = new ArrayList<>();
			int r=i,c=0;
			while (!isOut(r,c,mat)){
				list.add(mat[r][c]);
				c++;
				r++;
			}
			Collections.sort(list);
			r=i;
			c=0;
			while (!isOut(r,c,mat)){
				mat[r][c]=list.get(c);
				c++;
				r++;
			}
		}
		return mat;
    }
	public boolean isOut(int i,int j,int [][] mat){
		return i>=mat.length||j>=mat[0].length;
	}

	/*从右上角往左下角遍历，对角线的元素坐标满足i-j=常数k
	对同一条对角线，知道i，就可以通过k得到下标j=i-k
	i的最小值，令k=i-j,j=0，得到i=k,所以i的最小值为max(k,0)
	i的最大值，令k=i-j,j=n-1，得到i=k+n-1,所以i的最大值为min(k+n-1,m-1)
	枚举所有的i，左闭右开[max(k,0),min(k+n,m))
	，把对角线上的元素放入数组a，对a排序，再放回原数组
	 */
	public int[][] diagonalSort(int[][] mat) {
		int m = mat.length;
		int n = mat[0].length;
		int[] a = new int[Math.min(m, n)];
		for (int k = 1 - n; k < m; k++) { // k = i - j
			int leftI = Math.max(k, 0);
			int rightI = Math.min(k + n, m);
			for (int i = leftI; i < rightI; i++) {
				a[i - leftI] = mat[i][i - k];
			}
			Arrays.sort(a, 0, rightI - leftI);
			for (int i = leftI; i < rightI; i++) {
				mat[i][i - k] = a[i - leftI];
			}
		}
		return mat;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
